package com.atguigui.leetcode1;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

/**
 * 1096.花括号展开 II
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/3/7 8:43
 */
public class P1096BraceExpansionIi {
    public static void main(String[] args) {
        Solution solution = new P1096BraceExpansionIi().new Solution();
        // TO TEST
        solution.braceExpansionII("{{a,z},a{b,c},{ab,z}}");
    }

    class Solution {

        String expression;
        int idx;

        public List<String> braceExpansionII(String expression) {
            this.expression = expression;
            this.idx = 0;
            Set<String> ret = expr();
            return new ArrayList<String>(ret);
        }

        /*
        item 函数，根据当前字符是不是左括号来求解。如果是左括号，则调用 expr，返回结果；
        否则构造一个只包含当前字符的字符串集合，返回结果。
         */
        private Set<String> item() {
            Set<String> ret = new TreeSet<String>();
            if (expression.charAt(idx) == '{') {
                idx++;
                //一个大括号继续进入循环
                ret = expr();
            } else {
                StringBuilder sb = new StringBuilder();
                sb.append(expression.charAt(idx));
                ret.add(sb.toString());
            }
            idx++;
            return ret;
        }

        /*
        term 函数，不断的调用 item，并与其结果求积。
        如果匹配到表达式末尾或者当前字符不是小写字母，并且也不是左括号时，则返回。
         */
        private Set<String> term() {
            Set<String> ret = new TreeSet<String>() {{
                add("");
            }};
            // item 的开头是 { 或小写字母，只有符合时才继续匹配
            while (idx < expression.length()
                    && (expression.charAt(idx) == '{' || Character.isLetter(expression.charAt(idx)))) {
                Set<String> sub = item();
                Set<String> tmp = new TreeSet<String>();
                //求笛卡尔集
                for (String left : ret) {
                    for (String right : sub) {
                        tmp.add(left + right);
                    }
                }
                ret = tmp;
            }
            return ret;
        }

        /*
        expr 函数，不断的调用 term，并与其结果进行合并。
        如果匹配到表达式末尾或者当前字符不是逗号时，则返回。
         */
        private Set<String> expr() {
            Set<String> ret = new TreeSet<String>();
            while (true) {
                // 与 term() 求解结果求并集
                ret.addAll(term());
                // 如果匹配到逗号则继续，否则结束匹配
                if (idx < expression.length() && expression.charAt(idx) == ',') {
                    idx++;
                    continue;
                } else {
                    break;
                }
            }

            return ret;
        }
    }
}
